import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Work {
    public static int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }



    public static int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int l = 0, r = price[price.length - 1] - price[0];
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(price, k, mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private static boolean check(int[] price, int k, int x) {
        int cnt = 0, pre = -x;
        for (int cur : price) {
            if (cur - pre >= x) {
                pre = cur;
                ++cnt;
            }
        }
        return cnt >= k;
    }


    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i,x);
            dfs(x + 1);
            swap(i,x);
        }
    }

    void swap(int a,int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }



    public static int maxRepOpt1(String text) {
        int[] cnt = new int[26];
        int n = text.length();
        for (int i = 0; i < n; ++i) {
            ++cnt[text.charAt(i) - 'a'];
        }
        int ans = 0, i = 0;
        while (i < n) {
            int j = i;
            while (j < n && text.charAt(j) == text.charAt(i)) {
                ++j;
            }
            int l = j - i;
            int k = j + 1;
            while (k < n && text.charAt(k) == text.charAt(i)) {
                ++k;
            }
            int r = k - j - 1;
            ans = Math.max(ans, Math.min(l + r + 1, cnt[text.charAt(i) - 'a']));
            i = j;
        }
        return ans;
    }


    public static int lastRemaining(int n, int m) {
        int x = 0;
        for(int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }

    public static int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int n = reward1.length;
        int[] diffs = new int[n];   // 差值数组
        int maxScore = 0;           // 初始化最大得分
        for(int i = 0; i < n; i++){
            maxScore += reward2[i];                 // 累加reward2的元素作为初始化
            diffs[i] = reward1[i] - reward2[i];     // 生成差值数组
        }
        Arrays.sort(diffs);     // 对差值数组进行排序，java默认是升序排序
        for(int j = n - 1; j >= n - k; j--){
            maxScore += diffs[j];   // 更新最大得分
        }
        return maxScore;
    }

    public static void main(String[] args) {
        int[] nums1 = {1,1,3,4};
        int[] nums2 = {4,4,1,1};
        System.out.println(miceAndCheese(nums1, nums2, 3));
    }

    public static void main4(String[] args) {
        System.out.println(lastRemaining(5, 3));
    }

    public static void main3(String[] args) {
        String text = "aaabbaaa";
        System.out.println(maxRepOpt1(text));
    }

    public static void main2(String[] args) {
        int[] price = {13,5,1,8,21,2};
        int k = 3;
        System.out.println(maximumTastiness(price, k));
    }



    public static void main1(String[] args) {
//        int n = 23104;
//        System.out.println(countDigitOne(n));
//        System.out.println();
    }
}
